package easy;

public class Solution_572 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root==null && subRoot !=null) {
            return false;
        }
        if (subRoot==null || same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    private boolean same(TreeNode node, TreeNode sub) {
        if (node == null && sub == null) {
            return true;
        } else if (node==null || sub == null) {
            return false;
        } else if (node.val == sub.val && same(node.left, sub.left) && same(node.right, sub.right)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution_572 model = new Solution_572();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
//        root.left.right.left = new TreeNode(0);
        root.right = new TreeNode(5);

        TreeNode sub = new TreeNode(4);
        sub.left = new TreeNode(1);
        sub.right = new TreeNode(2);

        System.out.println(model.isSubtree(root, sub));
    }

    public static class TreeNode {
        public int val;
        public  TreeNode left;
        public TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
